class Solution {
    /*
        找到中点，逆置中点后的链表（可以不用判断链表长度的奇偶性），向两边遍历即可
    */
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return false;
        if(head.next == null)
            return true;
        // 找到终点
        ListNode midNode = findMid(head);// 找到终点后可以不用把中点前和链表和中点断开
        // 反转链表
        midNode = reverse(midNode);
        // 比较即可
        while(head!=null && midNode!=null){
            if(head.val!=midNode.val)
                return false;
            head = head.next;
            midNode = midNode.next;
        }
        return true;
    }
    // 找到终点
    public ListNode findMid(ListNode head){
        ListNode low = head;
        while( head!=null && head.next!=null ){
            low = low.next;
            head = head.next.next;
        }
        return low;
    }
    // 逆置链表
    public ListNode reverse(ListNode head){
        if(head==null || head.next==null)
            return head;
        ListNode tmp = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }
}